package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;


public class BrentFactorization {

    /**
     * 欧几里得算法求最大公约数
     * @param m 第一个数
     * @param n 第二个数
     * @return 最大公约数
     */
    public static long gcd(long m, long n) {
        if (m < n) {
            long temp = m;
            m = n;
            n = temp;
        }
        while (m % n != 0) {
            long temp = m;
            m = n;
            n = temp % n;
        }
        return n;
    }

    /**
     * Pollard Rho的核心函数 f(x) = (x² + c) mod n
     * @param x 自变量
     * @param c 常数
     * @param n 模数
     * @return 计算结果
     */
    public static long f(long x, long c, long n) {
        return (x * x + c) % n;
    }

    /**
     * 因子分解主函数，接收自定义分解函数
     * @param n 待分解的数
     * @param facFun 分解函数接口实现
     * @return 质因子列表（升序）
     */
    public static List<Long> factorization(long n, FactorFunction facFun) {
        List<Long> factors = new ArrayList<>();
        List<Long> stack = new ArrayList<>();
        stack.add(n);

        while (!stack.isEmpty()) {
            long x = stack.remove(stack.size() - 1); // 模拟Python的pop()
            if (x == 2) {
                factors.add(0, x); // 插入到列表头部，保持升序
                continue;
            }

            long[] pq;
            if ((x & 1) == 1) { // 奇数，使用自定义分解函数
                pq = facFun.apply(x);
            } else { // 偶数，直接分解出2
                pq = new long[]{2, x / 2};
            }

            long p = pq[0];
            long q = pq[1];
            if (p == 1) {
                factors.add(0, q);
            } else {
                stack.add(p);
                stack.add(q);
            }
        }
        return factors;
    }

    /**
     * Brent算法实现Pollard Rho分解（优化版判环）
     * @param n 待分解的数
     * @return 分解结果数组 [p, q]，无法分解则返回 [1, n]
     */
    public static long[] brent(long n) {
        long c = 1;
        long x0 = 2;
        long slow = x0;
        long fast = f(x0, c, n); // fast初始为f(x0, c, n)
        long power = 1;
        long steps = 1;

        while (true) {
            long diff = Math.abs(fast - slow);
            if (diff != 0) {
                long g = gcd(diff, n);
                if (g > 1) {
                    return new long[]{g, n / g};
                }
            } else {
                // 出现循环，未找到因子
                return new long[]{1, n};
            }

            if (steps == power) {
                power <<= 1; // power *= 2
                steps = 0;
                fast = slow; // fast重置为当前slow
            }

            slow = f(slow, x0, n); // 注意：此处c使用x0（与Python代码一致）
            steps += 1;
        }
    }

    public static void main(String[] args) {
        long n = 2206637L;
        // 传递brent分解函数作为参数
        List<Long> factors = factorization(n, BrentFactorization::brent);
        System.out.println(factors); // 输出 [317, 6961]
    }
}